template<class K> struct HashFun
{
    size_t operator()(const K& key)
    {
        return (size_t)key;
    }
};

template<> struct HashFun<string>
{
    size_t operator()(const string& s)
    {
        size_t num = 0;
        for (size_t i = 0; i < s.size(); i++)
        {
            num *= 131;
            num += s[i];
        }
        return num;
    }
};

namespace HashBucket
{
    template<class T>
    struct HashNode
    {
        HashNode<T>* _next;
        T _data;

        HashNode(const T& data)
            :_next(nullptr)
            , _data(data)
        {}
    };

    template<class K, class T, class Hash, class KeyOfT>
    class HashTable;

    template<class K, class T, class Hash, class KeyOfT>
    struct __hashtable_iterator
    {
        typedef __hashtable_iterator<K, T, Hash, KeyOfT> Self;
        typedef HashNode<T> Node;
        typedef HashTable<K, T, Hash, KeyOfT> HT;
        typedef T& reference;
        typedef T* pointer;

        Node* _cur;
        HT* _ht;

        __hashtable_iterator(Node* node, HT* ht) :_cur(node), _ht(ht) {}

        bool operator==(const Self& it) { return _cur == it._cur; }
        bool operator!=(const Self& it) { return _cur != it._cur; }

        reference operator*() { return _cur->_data; }
        pointer operator->() { return &(_cur->_data); }

        Self& operator++()
        {
            Hash hash;
            KeyOfT kft;

            if (_cur->_next)
            {
                _cur = _cur->_next;
            }
            else
            {
                size_t hashi = hash(kft(_cur->_data)) % _ht->TablesSize();
                size_t i = hashi + 1;
                for (; i < _ht->TablesSize(); i++)
                {
                    if (_ht->_tables[i])
                    {
                        _cur = _ht->_tables[i];
                        break;
                    }
                }

                if (i == _ht->TablesSize())
                    _cur = nullptr;
            }
            return *this;
        }
        Self operator++(int)
        {
            Self tmp(_cur, _ht);
            ++ (*this);
            return tmp;
        }
    };

    template<class K, class T, class Hash, class KeyOfT>
    class HashTable
    {
        typedef HashNode<T> Node;

        template<class K, class T, class Hash, class KeyOfT>
        friend struct __hashtable_iterator;

    public:

        typedef __hashtable_iterator<K, T, Hash, KeyOfT> iterator;

        iterator begin()
        {
            for (size_t i = 0; i < _tables.size(); i++)
                if (_tables[i])
                    return iterator(_tables[i], this);

            return iterator(nullptr, this);
        }
      
        iterator end() { return iterator(nullptr, this); }

        pair<iterator, bool> insert(const T& data)
        {
            Hash hash;
            KeyOfT kft;

            iterator ret = find(kft(data));
            if (ret != end())
                return make_pair(ret, false);

            if (_size == _tables.size())
            {
                vector<Node*> newTables;
                newTables.resize(__stl_next_prime(TablesSize()), nullptr);

                for (size_t i = 0; i < _tables.size(); i++)
                {
                    Node* cur = _tables[i];

                    while (cur)
                    {
                        size_t hashi = hash(kft(cur->_data)) % newTables.size();
                        cur->_next = newTables[hashi];
                        newTables[hashi] = cur;
                        cur = cur->_next;
                    }

                    _tables[i] = nullptr;
                }

                _tables.swap(newTables);
            }

            size_t hashi = hash(kft(data)) % _tables.size();
            Node* newnode = new Node(data);
            newnode->_next = _tables[hashi];
            _tables[hashi] = newnode;
            _size++;

            return make_pair(iterator(newnode, this), true);
        }

        bool erase(const K& key)
        {
            if (!find(key)._cur)
                return false;

            Hash hash;
            KeyOfT kft;
            size_t hashi = hash(key) % _tables.size();
            Node* cur = _tables[hashi], *prev = nullptr;

            while (cur)
            {
                if (kft(cur->_data) == key)
                {
                    if (cur == _tables[hashi])
                    {
                        Node* next = cur->_next;
                        delete cur;
                        _tables[hashi] = next;
                    }
                    else
                    {
                        prev->_next = cur->_next;
                        delete cur;
                    }
                    return true;
                }
                else
                    prev = cur;
                cur = cur->_next;
            }

            return true;
        }

        iterator find(const K& key)
        {
            if (empty())
                return iterator(nullptr, this);

            Hash hash;
            KeyOfT kft;

            size_t hashi = hash(key) % _tables.size();
            Node* cur = _tables[hashi];

            while (cur)
            {
                if (kft(cur->_data) == key)
                    return iterator(cur, this);
                cur = cur->_next;
            }

            return iterator(nullptr, this);
        }

        ~HashTable()
        {
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                if (_tables[i])
                {
                    Node* cur = _tables[i];
                    while (cur)
                    {
                        Node* next = cur->_next;
                        delete cur;
                        cur = next;
                    }
                }
            }
        }

        inline size_t __stl_next_prime(size_t n)
        {
            static const size_t __stl_num_primes = 28;
            static const size_t __stl_prime_list[__stl_num_primes] =
            {
                53, 97, 193, 389, 769,
                1543, 3079, 6151, 12289, 24593,
                49157, 98317, 196613, 393241, 786433,
                1572869, 3145739, 6291469, 12582917, 25165843,
                50331653, 100663319, 201326611, 402653189, 805306457,
                1610612741, 3221225473, 4294967291
            };

            for (size_t i = 0; i < __stl_num_primes; ++i)
                if (__stl_prime_list[i] > n)
                    return __stl_prime_list[i];

            return -1;
        }

        size_t size() const { return _size; }
        size_t TablesSize() const { return _tables.size(); }
        size_t BucketNum() const
        {
            size_t num = 0;
            for (size_t i = 0; i < TablesSize(); i++)
                if (_tables[i])
                    num++;
            return num;
        }
        size_t MaxBucketLenth() const
        {
            size_t maxlen = 0;
            for (size_t i = 0; i < TablesSize(); i++)
            {
                Node* cur = _tables[i];
                size_t bktlen = 0;
                while (cur)
                {
                    bktlen++;
                    cur = cur->_next;
                }
                maxlen = max(maxlen, bktlen);
            }
            return maxlen;
        }

        bool empty() const { return size() == 0; }

    private:
        vector<Node*> _tables;
        size_t _size;
    };
}

